# Algorithm complexity
# 算法复杂度
# 一种衡量算法优劣的方式、方法
# 空间复杂度：算法执行时占用的内存，随着输入规模的增大而变化的过程
# 时间复杂度：算法执行时占用的时间，随着输入规模的增大而变化的过程
# Big-O notation
# O()

# 写一个手动排序的函数
# 让 l 从小到达排序
# def sort(l: list):
#     pass

def sort(l: list):
    n = len(l) # 6
    for i in range(n):
        for j in range(0, n - i - 1):
            if l[j] > l[j+1]:
                l[j], l[j+1] = l[j+1], l[j]
    return l
# i = 0, j = n - 1
# i = 1, j = n - 1 - 1
# i = 2, j = n - 2 - 1
# ...
# i = n - 1, j = n - (n - 1) - 1 = 0

#  vj
# [1, 2, 5, 6, 7, 9]
#                 ^i
print(sort([6, 1, 2, 7, 5, 9]))

# 时间复杂度：O(1) test 的执行时间，不随着 l 的增长而变化
# 空间复杂度：O(1) test 执行时占用的内存，不随着 l 的增长而变化
def test(l: list):
    return 1

# 从列表中查找某个元素的位置
# 从 l 里找到 target 元素的索引
# 如果找到了，就返回这个位置，否则就返回 -1
# 时间复杂度：O(n) n 等于 l 的长度
# 空间复杂度：O(1) 常数复杂度，find 算法执行时占用的内存，不随着 l 的增长而增长
def find(l: list, target: int) -> int:
    # l 0 ~ len(l) - 1
    #tmp = []
    for i in range(0, len(l)):
        #tmp.append(l[i])
        if l[i] == target:
            return i
    
    return -1

# 假设 l 是一个已经排序好的列表
# 从 l 里找到 target 元素的索引
# 如果找到了，就返回这个位置，否则就返回 -1
#  0                       8
# [1, 2, 3, 4, 5, 6, 7, 8, 9] 11
# [[1, 2, 3, 4, 5] [6, 7, 8, 9]
#                   5        8
#                  [6, 7] [8, 9] 11
#                          7  8
#                         [8] [9]
#                             [9] left <= right
# 二分查找
def binarySearch(l: list, target: int) -> int:
    left = 0
    right = len(l) - 1

    while left <= right:
        mid = (left + right) // 2

        if l[mid] == target:
            return mid
        
        if l[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1
